package com.shuang.tree33;

import java.util.HashMap;
import java.util.Map;

public class BulidTree {

    //递归实现 思路与从中序后序一样 这次先取前序第一个元素 是中节点
    Map<Integer, Integer> map; //将中序数组中元素值和索引位置存起来 便于根据后序元素值查找中序数组中元素索引位置

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        //先判断 数组为空时 直接返回空即可
        if (inorder.length == 0 || preorder.length == 0) {
            return null;
        }

        //将map中存好值
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }

        //采取索引左闭右开的原则
        TreeNode root = findNode(inorder, 0, inorder.length, preorder, 0, preorder.length);
        return root;
    }

    //递归 构建树 索引左闭右开原则
    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] preorder, int preBegin, int preEnd) {
        // 参数里的范围都是左闭右开
        if (inBegin >= inEnd || preBegin >= preEnd) { // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }

        //根据前序数组第一个的元素 找到在中序数组该元素位置
        int rootValue = preorder[preBegin];
        //该元素在中序数组中的索引位置
        int index = map.get(rootValue);

        //并根据该元素构建节点（中节点）
        TreeNode root = new TreeNode(rootValue);

        //拿到中序数组左子树元素个数 根据左子树个数 切割后续数组
        int leftNum = index - inBegin;

        //根据索引下标直接切割中序数组和前序数组(坚持左闭右开原则) 分成左右子树 对切割好的数组 左子树和右子树进行递归
        //左子树 ：中序数组索引 从开始到索引位置[) 前序从开始的下一个  到加上左子树元素个数位置
        root.left = findNode(inorder, inBegin, index, preorder, preBegin + 1, preBegin + 1 + leftNum);
        root.right = findNode(inorder, index + 1, inEnd, preorder, preBegin + 1 + leftNum, preEnd);

        return root;

    }
}
